#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 100;
const int INF = 1000;

struct edge
{ int v;
  int x;
};

vector<edge> a[NMAX];
int n;
int s;

int d[NMAX];


void init()
{ int m;
  ifstream fin("G1.txt");
  fin >> n >> m;
  
  for(int i=0; i<m; i++)
  { int u;
    edge e;
    fin >> u >> e.v >> e.x;
    a[u].push_back(e);
  }
  
  fin >> s;
}

void dijkstra()
{
  for(int u=1; u<=n; u++)
    d[u] = INF;
  d[s] = 0;
  
  int T[NMAX];
  for(int i=1; i<=n; i++)
    T[i]=i;
    
  for(int k=n; k>0; k--)
  { cout << "T: ";
    for(int i=1; i<=k; i++)
      cout << T[i] << " ";
    cout << endl;  
    
    int p=1;
    int u=T[p];
    int dmin=d[u];
    
    for(int i=2; i<=k;i++)
    {
      if(d[T[i]]<dmin)
        {
          p=i;
          u=T[i];
          dmin=d[u];
        }
    }

    swap(T[p],T[k]);

    int cnt=a[u].size();
     for(int i=0; i<cnt; i++)
    { 
      edge e = a[u][i];
      int v=e.v;
      int x=e.x;
      if(d[v]>d[u]+x)
        d[v]=d[u]+x;
    }
    cout << "u=" << u << endl;
    cout << "d: ";
    for(int u=1; u<=n; u++)
      cout << d[u] << " ";
    cout << endl;  
  }
  
}


int main()
{ init();
  
/*
  for(int u=1; u<=n; u++)
  { cout << u << ": ";
    int k=a[u].size();
    for(int i=0; i<k; i++)
    { edge e = a[u][i];
      cout << e.v << " " << e.x << ";" ;
    }
    cout << endl;
  }
  cout << "s = " << s << endl;
*/

  dijkstra();

  for(int u=1; u<=n; u++)
    cout << u << " " << d[u] << endl;

  return 0;
}
